package LeetCode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}14:43
 */
public class LeetCode337 {

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }

  // 上面两种解法用到了孙子节点，计算爷爷节点能偷的钱还要同时去计算孙子节点投的钱，虽然有了记忆化，但是还是有性能损耗。
  //
  //我们换一种办法来定义此问题
  //
  //每个节点可选择偷或者不偷两种状态，根据题目意思，相连节点不能一起偷
  //
  //当前节点选择偷时，那么两个孩子节点就不能选择偷了
  //当前节点选择不偷时，两个孩子节点只需要拿最多的钱出来就行(两个孩子节点偷不偷没关系)
  //我们使用一个大小为 2 的数组来表示 int[] res = new int[2] 0 代表不偷，1 代表偷
  //任何一个节点能偷到的最大钱的状态可以定义为
  //
  //当前节点选择不偷：当前节点能偷到的最大钱数 = 左孩子能偷到的钱 + 右孩子能偷到的钱
  //当前节点选择偷：当前节点能偷到的最大钱数 = 左孩子选择自己不偷时能得到的钱 + 右孩子选择不偷时能得到的钱 + 当前节点的钱数
    public int rob(TreeNode treeNode){
        int[] result = robInternal(treeNode);
        return Math.max(result[0],result[1]);
    }

    public int[] robInternal(TreeNode node){
        if (node == null){
            return new int[2];
        }
        int[] result = new int[2];

        int[] left = robInternal(node.left);
        int[] right = robInternal(node.right);

        // 不偷当前节点的时候 其子节点可以选择偷或者不偷
        result[0] = Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        // 偷当前节点的时候 其子节点只能选择不偷
        result[1] = left[0] + right[0] + node.val;
        return result;
    }


    // 方法一：最优子结构 可以将情况分为一个爷爷辈+4个孙子 与 两个儿子 的钱作比较
    public int rob1(TreeNode root){
        if (root == null){
            return 0;
        }

        int money = root.val;
        if (root.left != null){
            money += rob1(root.left.left) + rob(root.left.right);
        }
        if (root.right != null){
            money += rob1(root.right.left) + rob(root.right.right);
        }

        return Math.max(money,rob1(root.left) + rob1(root.right));
    }

    // 方法二：引入记忆集-解决重复子问题 以前使用数组 这里使用一个hash表来存放已有的结果
    public int rob2(TreeNode root){
        Map<TreeNode,Integer> map = new HashMap<>();
        return robInternal(root,map);
    }

    public int robInternal(TreeNode root,Map<TreeNode,Integer> map){
        if (root == null){
            return 0;
        }
        if (map.containsKey(root)){
            return map.get(root);
        }

        int meney = root.val;
        if (root.left != null){
            meney += robInternal(root.left.left,map) + robInternal(root.left.right,map);
        }
        if (root.right != null){
            meney += robInternal(root.right.left,map) + robInternal(root.right.right,map);
        }
        int resrlut = Math.max(meney,robInternal(root.left,map) + robInternal(root.right,map));
        map.put(root,resrlut);
        return resrlut;
    }


}
